// Vahe and Arman
#include "BTreeNode.h"
#include <iostream>

using namespace std;


// BTLeafNode constructor
BTLeafNode::BTLeafNode()
{
	// initialize the buffer to 0
	memset(buffer, 0, PageFile::PAGE_SIZE);
}
/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{ 
	memset(buffer, 0, PageFile::PAGE_SIZE);
	return pf.read(pid, buffer); 
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{ 
	return pf.write(pid, buffer); 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{
	// num records are stored in the first 4 bytes of page
	int numKey;
	memcpy(&numKey, &buffer, sizeof(int));
	return numKey;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{
	if(getKeyCount() >= 84) 
		return RC_NODE_FULL;

	int i, ourKey;
	char* ptr = &(buffer[0]);
	int slotSize = sizeof(RecordId) + sizeof(int);
	int totSize = getKeyCount() * slotSize;
	ptr += sizeof(int);
	ptr += sizeof(PageId);

	while (ptr) 
	{
		memcpy(&ourKey, ptr, sizeof(int));
		if(ourKey == 0) break;
		if (ourKey < key)
		{
			ptr += slotSize;
			i++;
		} 
		else break;
	}

	if (&(buffer[PageFile::PAGE_SIZE]) - ptr < 20) 
		return RC_NODE_FULL;

	char* temp = (char*)malloc(PageFile::PAGE_SIZE * sizeof(char));
	memset(temp, 0, PageFile::PAGE_SIZE);
	if(totSize > 0 && ourKey != 0) 
	{
		memcpy(temp, ptr, totSize - (slotSize * i));
		memset(ptr, 0, totSize - (slotSize * i));
	}

	memcpy(ptr, &key, sizeof(int));
	ptr += sizeof(int);
	memcpy(ptr, &rid, sizeof(RecordId));

	ptr += sizeof(RecordId);
	if(totSize > 0 && ourKey != 0)
		memcpy(ptr, temp, totSize - (slotSize * i));
	free(temp);

	//set the count of our key = current key
	int outKeyCount = getKeyCount();
	outKeyCount++;
	ptr = &(buffer[0]);
	memcpy(ptr, &outKeyCount, sizeof(int));
	return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{
	int slotSize = sizeof(RecordId) + sizeof(int);
	int totSize = getKeyCount() * slotSize;
	int i = 0;
	int retval = 0;

	char* ptr = &(buffer[0]);
	ptr += sizeof(int);
	ptr += sizeof(PageId);

	while(i < (getKeyCount() / 2)) 
	{
		ptr += slotSize;
		i++;
	}
	
	char* temp = (char*)malloc(1024*sizeof(char));
	char* head = temp;
	memset(temp, 0, 1024*sizeof(char));
	memcpy(temp, ptr, totSize - (slotSize * (getKeyCount()/2)));
	memset(ptr, 0, totSize - (slotSize * (getKeyCount()/2)));
	int newKey = getKeyCount() / 2;
	memcpy(buffer, &newKey, sizeof(int));

	while(temp) 
	{
		int k;
		RecordId r;
		memcpy(&k, temp, sizeof(int));
		if(k == 0) break;
		temp += sizeof(int);
		memcpy(&r, temp, sizeof(RecordId));
		temp += sizeof(RecordId);
		if(r.sid == 0 && r.pid == 0 && k != 272) 
			int q = r.sid;
		if( sibling.insert(k, r) != 0 ) 
		{
			free(head);
			return RC_FILE_WRITE_FAILED;
		}
	}
	free(head);
	RecordId r;
	if( sibling.readEntry(0, siblingKey, r) != 0) 
		return RC_FILE_READ_FAILED;
	if(key < siblingKey) 
	{
		if( insert(key, rid) != 0 ) 
			return RC_FILE_WRITE_FAILED;
	} 
	else
	{
		if( sibling.insert(key, rid) != 0 )
			return RC_FILE_WRITE_FAILED;
	}
	if( sibling.readEntry(0, siblingKey, r) != 0)
		return RC_FILE_READ_FAILED;
	return retval;
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{
	int slotSize = sizeof(RecordId) + sizeof(int);
	int totSize = getKeyCount() * slotSize;
	char* ptr = &(buffer[0]);
	int curr_key;
	int i = 0;
	ptr += sizeof(int);

	while(ptr) 
	{
		memcpy(&curr_key, ptr, sizeof(int));
		if(curr_key >= searchKey || curr_key == 0) 
		{
			eid = i;
			break;
		}
		i++;
		ptr += slotSize;
	}
	return 0;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{
	int slotSize = sizeof(RecordId) + sizeof(int);
	int totSize = getKeyCount() * slotSize;
	char* ptr = &(buffer[0]);
	int i = 0;

	ptr += sizeof(int);
	ptr += sizeof(PageId);
	while(ptr && i < eid)
	{
		ptr += slotSize;
		i++;
	}
	memcpy(&key, ptr, sizeof(int));
	ptr += sizeof(int);
	memcpy(&rid, ptr, sizeof(RecordId));
	return 0;
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{
	PageId pid;
	char* ptr = &(buffer[0]);
	ptr += sizeof(int);
	memcpy(&pid, ptr, sizeof(PageId));
	return pid;
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{
	char* ptr = &(buffer[0]);
	ptr += sizeof(int);
	memcpy(ptr, &pid, sizeof(PageId));
	return 0;
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */

BTNonLeafNode::BTNonLeafNode() 
{
	memset(buffer, 0, PageFile::PAGE_SIZE);
}

RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{
	return pf.read(pid, buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{ 
	return pf.write(pid, buffer); 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{
	int retval = 0;
	memcpy(&retval, &buffer, sizeof(int));
	return retval;
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{ 
	int slotSize = sizeof(PageId) + sizeof(int);
	int totSize = getKeyCount() * slotSize;
	char* ptr = &(buffer[0]);
	int i = 0;

	if(totSize >= PageFile::PAGE_SIZE - slotSize) 
	{
//		cout << "Non-Leaf node is full" << endl;
		return RC_NODE_FULL;
	}

	ptr += sizeof(int);
	ptr += sizeof(PageId);
	int currKey;
	
	
	while (ptr) 
	{
		memcpy(&currKey, ptr, sizeof(int));
		if(currKey == 0) break;	
		if (currKey < key) 
		{
			ptr += slotSize;
			i++;
		} 
		else break;
	}

	if(currKey == key) 
	{
		ptr += sizeof(int);
		memcpy(ptr, &pid, sizeof(PageId));
		return 0;
	}

	if (ptr == &(buffer[PageFile::PAGE_SIZE]))
		return RC_FILE_WRITE_FAILED;

	char* temp = (char*) malloc(PageFile::PAGE_SIZE * sizeof(char));
	memset(temp, 0, PageFile::PAGE_SIZE);

	if(totSize > 0 && currKey != 0) 
	{
		memcpy(temp, ptr, totSize - (slotSize * i));
		memset(ptr, 0, totSize - (slotSize * i));
	}
	memcpy(ptr, &key, sizeof(int));
	ptr += sizeof(int);
	memcpy(ptr, &pid, sizeof(PageId));
	ptr += sizeof(PageId);
	if(totSize > 0 && currKey != 0) 
		memcpy(ptr, temp, totSize - (slotSize * i));
	
	free(temp);
	int outKeyCount = getKeyCount();
	outKeyCount++;
	ptr = &(buffer[0]);
	memcpy(ptr, &outKeyCount, sizeof(int));
	return 0;
}

RC BTNonLeafNode::readEntry(int eid, int& key) 
{
	int slotSize = sizeof(PageId) + sizeof(int);
	int totSize = getKeyCount() * slotSize;
	int i = 0;
	char* ptr = &(buffer[0]);
	ptr += sizeof(int);

	while(ptr) 
	{
		ptr += sizeof(PageId);
		if(i == eid) 
		{
			memcpy(&key, ptr, sizeof(int));
			break;
		}
		ptr += slotSize;
	}
	return 0;
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{
	int slotSize = sizeof(PageId) + sizeof(int);
	int totSize = getKeyCount() * slotSize;
	int i = 0;

	char* ptr = &(buffer[0]);
	ptr += sizeof(int);

	while(i < (getKeyCount() / 2)) 
	{
		ptr += slotSize;
		i++;
	}
	//increment once more to get past the last record
	//ptr += slotSize;
	char* temp = (char*) malloc(PageFile::PAGE_SIZE * sizeof(char));
	char* head = temp;
	//save the last half of the data
	memset(temp, 0, 1024*sizeof(char));
	memcpy(temp, ptr, totSize - (slotSize * (getKeyCount() / 2)));

	//remove old data from current node
	memset(ptr, 0, totSize - (slotSize * (getKeyCount() / 2)));
	int newKey = getKeyCount() / 2;
	memcpy(buffer, &newKey, sizeof(int));

	//extract ALL the data from the original node
	//insert them into the new node using the insert function
	while(temp) 
	{
		int k;
		PageId p;
		memcpy(&k, temp, sizeof(int));
		if(k == 0) break;
		temp += sizeof(int);
		memcpy(&p, temp, sizeof(PageId));
		temp += sizeof(PageId);
		if( sibling.insert(k, p) != 0) 
		{
			free(head);
			return RC_FILE_WRITE_FAILED;
		}
	}

	free(head);
	if( sibling.readEntry(0, midKey) != 0 )
		return RC_FILE_READ_FAILED;

	//insert the new key that we're trying to insert
	if(key < midKey) 
	{
		if( insert(key, pid) != 0 )
			return RC_FILE_WRITE_FAILED;
	}
	else 
	{
		if( sibling.insert(key, pid) != 0 )
			return RC_FILE_WRITE_FAILED;
	}
	return 0;
}
/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{
	int slotSize = sizeof(PageId) + sizeof(int);
	int totSize = getKeyCount() * slotSize;
	char* ptr = &(buffer[0]);
	int curr_key;

	ptr += sizeof(int);
	ptr += sizeof(int);

	while(ptr) 
	{
		memcpy(&curr_key, ptr, sizeof(int));
		if(curr_key != 0 && curr_key < searchKey) 
			ptr += sizeof(int);
		else 
		{
			ptr -= sizeof(PageId);
			memcpy(&pid, ptr, sizeof(PageId));
			break;
			}
		ptr += slotSize;
	}
	return 0;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{
	char* ptr = &(buffer[0]);
	int k = 1;
	ptr += sizeof(int);

	memcpy(ptr, &pid1, sizeof(PageId));
	ptr += sizeof(PageId);
	memcpy(ptr, &key, sizeof(int));
	ptr += sizeof(int);
	memcpy(ptr, &pid2, sizeof(PageId));
	memcpy(buffer, &k, sizeof(int));
	return 0;
}
